#include "rbtree.h"
#include "common.h"
#include "queue.h"

/* 左旋 */
static void RBTree_left_rotate(RB_TREE* rbtree, RB_Node* grand);
/* 右旋 */
static void RBTree_right_rotate(RB_TREE* rbtree, RB_Node* grand);
/* 插入后的平衡调整 */
static void RBTree_Insert_Fixup(RB_TREE* rbtree, RB_Node* cur);

/* 红黑树初始化 */
int RBTree_Init(RB_TREE** rbtree, int compareFunc(void* val1, void* val2), void printFunc(void* val))
{
    RB_TREE* tmp = (RB_TREE*)malloc(sizeof(RB_TREE));
    if(tmp == NULL)
    {
        return MALLOC_ERROR;
    }

    tmp->nil = (RB_Node*)malloc(sizeof(RB_Node));
    if(tmp->nil == NULL)
    {
        return MALLOC_ERROR;
    }
    tmp->nil->color = Black;
    tmp->nil->parent = tmp->nil;
    tmp->nil->left = tmp->nil;
    tmp->nil->right = tmp->nil;

    tmp->root = tmp->nil;
    tmp->compareFunc = compareFunc;
    tmp->printFunc = printFunc;
    *rbtree = tmp;
    return 0;
}

/* 左旋 */
static void RBTree_left_rotate(RB_TREE* rbtree, RB_Node* grand)
{
    RB_Node* parent = grand->right;
    grand->right = parent->left;
    if(parent->left != rbtree->nil)
    {
        parent->left->parent = grand;
    }
    parent->left = grand;
    parent->parent = grand->parent;
    if(parent->parent != rbtree->nil)
    {
        if(grand == grand->parent->left)
        {
            parent->parent->left = parent;
        }
        else if(grand == grand->parent->right)
        {
            parent->parent->right = parent;
        }
    }
    else
    {
        rbtree->root = parent;
    }
    grand->parent = parent;
}

/* 右旋 */
static void RBTree_right_rotate(RB_TREE* rbtree, RB_Node* grand)
{
    RB_Node* parent = grand->left;
    grand->left = parent->right;
    if(parent->right != rbtree->nil)
    {
        parent->right->parent = grand;
    }
    parent->right = grand;
    parent->parent = grand->parent;
    if(grand->parent != rbtree->nil)
    {
        if(grand == grand->parent->right)
        {
            parent->parent->right = parent;
        }
        else if(grand == grand->parent->left)
        {
            parent->parent->left = parent;
        }
    }
    else
    {
        rbtree->root = parent;
    }

    grand->parent = parent;
}
/* 插入后的平衡调整 */
static void RBTree_Insert_Fixup(RB_TREE* rbtree, RB_Node* cur)
{
    while(cur->parent->color == Red)
    { 
        /* 父左 */
        if(cur->parent == cur->parent->parent->left)
        {
            RB_Node* uncle = cur->parent->parent->right;
            if(uncle->color == Red)//父左叔右红
            {
                cur->parent->color = Black;
                uncle->color = Black;
                cur->parent->parent->color = Red;
                cur = cur->parent->parent;
            }
            else
            {   
                if(cur == cur->parent->right)//LR
                {
                    cur = cur->parent;
                    RBTree_left_rotate(rbtree, cur);   

                }
                cur->parent->color = Black;
                cur->parent->parent->color = Red;
                RBTree_right_rotate(rbtree, cur->parent->parent);
            }
        }
        else
        {/* 父右 */
            RB_Node* uncle = cur->parent->parent->left;
            if(uncle->color == Red)
            {
                uncle->color = Black;
                cur->parent->color = Black;
                cur->parent->parent->color = Red;  
                cur = cur->parent->parent;              
            }
            else
            {
                if(cur == cur->parent->left)//RL
                {
                    cur = cur->parent;
                    RBTree_right_rotate(rbtree, cur);
                }
                cur->parent->color = Black;
                cur->parent->parent->color = Red;
                RBTree_left_rotate(rbtree, cur->parent->parent);
            }
        }
    }

    rbtree->root->color = Black;
}

/* 红黑树插入 */
int RBTree_Insert(RB_TREE* rbtree, void* value)
{
    if(rbtree == NULL)
    {
        return NULL_PTR;
    }
    RB_Node* cur = rbtree->root;
    RB_Node* parent = rbtree->nil;
    
    while(cur != rbtree->nil)
    {
        parent = cur;
        int ret = rbtree->compareFunc(value, cur->val);
        if(ret == 1)
        {
            cur = cur->right;printf("->");
        }
        else if(ret == -1)
        {
            cur = cur->left;printf("<-");
        }
        else
        {
            return VALUE_EXIST;
        }
    }
    printf("\n");
    RB_Node* tmp = (RB_Node*)malloc(sizeof(RB_Node));
    tmp->parent = parent;
    tmp->val = value;
    if(parent == rbtree->nil)
    {
        rbtree->root = tmp;
    }
    else
    {
        if(rbtree->compareFunc(tmp->val, parent->val) == 1)
        {
            parent->right = tmp;
        }
        else
        {
            parent->left = tmp;
        }
    }

    tmp->color = Red;
    tmp->left = rbtree->nil;
    tmp->right = rbtree->nil;
    /* 插入后的平衡调整 */
    RBTree_Insert_Fixup(rbtree, tmp);
}

/* 红黑树获取元素 */
RB_Node* RBTree_Search(RB_TREE* rbtree, void* value)
{
    if(rbtree == NULL)
    {
        return NULL;
    }
    RB_Node* cur = rbtree->root;
    int ret = 2;
    while(cur != rbtree->nil)
    {
        ret = rbtree->compareFunc(value, cur->val);
        if(ret == 1)
        {
            cur = cur->right;
        }
        else if(ret == -1)
        {
            cur = cur->left;
        }
        else
        {
            return cur;
        }
    }

    return NULL;
}
/* 删除后的平衡调整 */
static void RBTree_Delete_Fixup(RB_TREE* rbtree, RB_Node* cur)
{
    while(cur->color == Black && cur != rbtree->root)
    {
        if(cur == cur->parent->left)
        {
            RB_Node* bro = cur->parent->right;
            if(bro->color == Red)//兄红，令其变黑
            {
                bro->color = Black;
                cur->parent->color = Red;
                RBTree_left_rotate(rbtree, cur->parent);
                bro = cur->parent->right;
            }

            if(bro->left->color == Black && bro->right->color == Black)
            {
                bro->color = Red;
                /* 此时父可能为黑，也可能为红，交给while处理 */
                cur = cur->parent;
            }
            else
            {
                if(bro->right->color == Black)//顺侄红，对侄黑
                {
                    bro->color = Red;
                    bro->left->color = Black;
                    RBTree_right_rotate(rbtree, bro);
                    bro = bro->parent;
                }
                /* 兄黑对侄红 *//* 思考下这里父为黑与父为红两种情形 */
                /* 以下这段代码满足父为黑和父为红两种情形 */
                bro->color = cur->parent->color;
                cur->parent->color = Black;
                bro->right->color = Black;
                RBTree_left_rotate(rbtree, cur->parent);
                break;
            }
        }
        else
        {
            RB_Node* bro = cur->parent->left;
            if(bro->color == Red)
            {
                bro->color = Black;
                cur->parent->color = Red;
                RBTree_right_rotate(rbtree, cur->parent);
                bro = cur->parent->left;
            }

            if(bro->left->color == Black && bro->right->color == Black)
            {
                bro->color = Red;
                cur = cur->parent;
            }
            else
            {
                if(bro->left->color == Black)
                {
                    bro->color = Red;
                    bro->right->color = Black;
                    bro = bro->parent;
                }
                bro->color = cur->parent->color;
                cur->parent->color = Black;
                bro->left->color = Black;
                RBTree_right_rotate(rbtree, cur->parent);
                break;
            }
        }
    }
    /* 被删节点Del为含一个红子节点的黑节点 */
    cur->color = Black;
}

/* 红黑树删除元素 */
int RBTree_Delete(RB_TREE* rbtree, void* value)
{
    if(rbtree == NULL)
    {
        return NULL_PTR;
    }
    //1
    RB_Node* cur = RBTree_Search(rbtree, value);
    
    if(cur == NULL)
    {
        return NOT_FIND;
    }
    RB_Node* Del = rbtree->nil;
    if(cur->left == rbtree->nil || cur->right == rbtree->nil)
    {
        Del = cur;
    }
    else
    {
        Del = cur->right;
        while(Del->left != rbtree->nil)
        {
            Del = Del->left;
        }
    }

    //2
    /* 到这里Del必定为度为0或者度为1 */
    if(cur != Del)
    {
        cur->val = Del->val;
    }
    /* Del为单个红节点或者单个黑节点或者带一个红子节点的黑节点 */
    RB_Node* child = rbtree->nil;
    if(Del->left != rbtree->nil)
    {
        child = Del->left;
    }
    else if(Del->right != rbtree->nil)
    {
        child = Del->right;
    }

    child->parent = Del->parent;

    if(Del->parent == rbtree->nil)
    {
        rbtree->root = child;
    }
    else if(Del == Del->parent->left)
    {
        Del->parent->left = child;
    }
    else if(Del == Del->parent->right)
    {
        Del->parent->right = child;
    }
    //3
    if(Del->color == Black)
    {
        /* 删除黑节点调整 */
        RBTree_Delete_Fixup(rbtree, child);
    }
    //4
    if(Del != NULL)
    {
        free(Del);
        Del == NULL;
    }
}

/* 层序遍历 */
int RBTree_LevelOrder(RB_TREE* rbtree)
{
    if(rbtree == NULL)
    {
        return NULL_PTR;
    }
    if(rbtree->root == NULL || rbtree->root == rbtree->nil)
    {
        return INVALID_ACCESS;
    }
    Queue* QueList = NULL;
    QueueInit(&QueList);
    QueuePush(QueList, (void*)rbtree->root);
    RB_Node* tmp = NULL;
    while(!QueueEmpty(QueList))
    {
        tmp = (RB_Node*)QueuePop(QueList);
        rbtree->printFunc(tmp->val);
        if(tmp->left != rbtree->nil)
        {
            QueuePush(QueList, (void*)tmp->left);
        }
        if(tmp->right != rbtree->nil)
        {
            QueuePush(QueList, (void*)tmp->right);
        }
    }
    printf("\n");
    QueueDestroy(QueList);
    return ON_SUCCESS;
}

int RBTree_LevelDestroy(RB_TREE* rbtree)
{
    if(rbtree == NULL)
    {
        return NULL_PTR;
    }
    if(rbtree->root == NULL)
    {
        return INVALID_ACCESS;
    }
    Queue* QueList = NULL;
    QueueInit(&QueList);
    if(rbtree->root != rbtree->nil)
    {
        QueuePush(QueList, (void*)rbtree->root);
    }
    RB_Node* tmp = NULL;
    while(!QueueEmpty(QueList))
    {
        printf("--------------\n");
        tmp = (RB_Node*)QueuePop(QueList);
        if(tmp->left != rbtree->nil)
        {
            QueuePush(QueList, (void*)tmp->left);
        }
        if(tmp->right != rbtree->nil)
        {
            QueuePush(QueList, (void*)tmp->right);
        }

        if(tmp != NULL)
        {
            free(tmp);
            tmp = NULL;
        }
    }
    QueueDestroy(QueList);
    if(rbtree->nil != NULL)
    {
        printf("nil~\n");
        free(rbtree->nil);
        rbtree->nil = NULL;
    }
    if(rbtree != NULL)
    {
        printf("rbtree~\n");
        free(rbtree);
        rbtree = NULL;
    }
    return ON_SUCCESS;
}